package top.minuy.structure.graph.sort;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;

/**
 * 拓扑排序
 *
 * @author Minuy
 * @time 13:13
 * @date 2021/11/27
 */
public class TopologicalSort {

    private boolean hasCycle;
    private ArrayList<Integer> res;

    public TopologicalSort(Graph g) {
        if (!g.isDirected()) {
            throw new IllegalArgumentException("TopologicalSort only works in directed graph.");
        }

        int[] idg = new int[g.V()];
        res = new ArrayList<>();

        ArrayList<Integer> queue = new ArrayList<>();

        // 找到入度为0的所有顶点
        for (int v = 0; v < g.V(); v++) {
            idg[v] = g.indegree(v);
            if (idg[v] == 0) {
                queue.add(v);
            }
        }


        while (!queue.isEmpty()) {
            int v = queue.remove(0);
            res.add(v);

            for (int w : g.adj(v)) {
                idg[w]--;
                if (idg[w] == 0) {
                    queue.add(w);
                }
            }
        }

        // TODO 只考虑联通图
        if (res.size() != g.V()) {
            res.clear();
            hasCycle = true;
        }
    }

    /**
     * 获取有向图有没有环
     *
     * @return boolean 有没有环
     * @author Minuy
     * @date 2021/11/27 13:53
     */
    public boolean hasCycle() {
        return hasCycle;
    }

    /**
     * 获取拓扑排序的结果
     *
     * @return Iterable<Integer> 拓扑排序的结果
     * @author Minuy
     * @date 2021/11/27 13:53
     */
    public Iterable<Integer> sortResult() {
        return res;
    }

    /*
    private TopologicalSort(){}

    public static int[] sort(Graph g){
        if (!g.isDirected()){
            throw new IllegalArgumentException("TopologicalSort only works in directed graph.");
        }

        int[] ret = new int[g.V()];
        int[] idg = new int[g.V()];

        ArrayList<Integer> queue = new ArrayList<>();

        // 找到入度为0的所有顶点
        for (int v=0;v<g.V();v++){
            idg[v] = g.indegree(v);
            if (idg[v] == 0){
                queue.add(v);
            }
        }

        int i=0;
        while (!queue.isEmpty()){
            int v = queue.remove(0);
            ret[i] = v;
            i++;

            for (int w:g.adj(v)){
                if (idg[w]!=0) {
                    idg[w]--;
                    if (idg[w] == 0) {
                        queue.add(w);
                    }
                }
            }

        }
        return ret;
    }*/
}
